//
// Created by jizhe hu on 2024/2/7.
//

#ifndef LEETCODE_PRIORITY_QUEUE_H
#define LEETCODE_PRIORITY_QUEUE_H
#include <vector>

class priority_queue {
private:
    std::vector<int> q;

public:
    int size() { return q.size(); }
    bool empty() { return q.empty(); }
    int top() { return q[0]; }

    int parent(int child) { return (child - 1) / 2; }
    int l_child(int parent) { return 2 * parent + 1; }
    int r_child(int parent) { return 2 * parent + 2; }
    void q_swap(int id1, int id2) {
        int tmp = q[id1];
        q[id1] = q[id2];
        q[id2] = tmp;
    }
    // 将新节点插入数组尾部，然后上浮
    void push(int x) {
        q.push_back(x);
        x = size() - 1;
        while(q[parent(x)] < q[x]) {
            q_swap(parent(x), x);
            x = parent(x);
            if(x <= 0) break;
        }
    }
    void pop() {
        q_swap(0, size() - 1);
        q.pop_back();
        int parent = 0;
        int child = q[l_child(parent)] > q[r_child(parent)] ? l_child(parent) : r_child(parent);
        while (q[parent] < q[child]) {
            q_swap(parent, child);
            parent = child;
            child = q[l_child(parent)] > q[r_child(parent)] ? l_child(parent) : r_child(parent);
            if(parent > size()) break;
        }
    }
};

#endif //LEETCODE_PRIORITY_QUEUE_H
